1. Field of the Invention
The present invention relates generally to multiple access digital communication systems. More specifically, the invention relates to a multiuser detector system and method for the simultaneous reception of data from multiple users having different spreading factors.
2. Description of the Related Art
A multiple-access communication system allows a plurality of users to access the same communication medium to transmit or receive information. The media may comprise, for example, a network cable in a local area network or Ian, a copper wire in the classic telephone system, or an air interface for wireless communication.
A prior art multiple access communication system is shown in FIG. 1. The communication media is referred to as a communication channel. Communication techniques such as frequency division multiple access or FDMA, time division multiple access or TDMA, carrier sense multiple access or CSMA, code division multiple access or CDMA and others allow access to the same communication medium for more than one user. These techniques can be mixed together creating hybrid varieties of multiple access schemes. For example, time division duplex or TDD mode of the proposed third generation W-CDMA standard is a combination of TDMA and CDMA.
An example CDMA prior art communication system is shown in FIG. 2. CDMA is a communication technique in which data is transmitted with a broadened band (spread spectrum) by modulating the data to be transmitted with a pseudo-noise signal. The data signal to be transmitted may have a bandwidth of only a few thousand Hertz distributed over a frequency band that may be several million Hertz. The communication channel is being used simultaneously by K independent subchannels. For each subchannel, all other subchannels appear as interference.
As shown, a single subchannel of a given bandwidth is mixed with a unique spreading code which repeats a predetermined pattern generated by a wide bandwidth, pseudo-noise (pn) sequence generator. These unique user spreading codes are typically pseudo-orthogonal to one another such that the cross-correlation between the spreading codes is close to zero. A data signal is modulated with the pn sequence producing a digital spread spectrum signal. A carrier signal is then modulated with the digital spread spectrum signal and transmitted in dependence upon the transmission medium. A receiver demodulates the transmission extracting the digital spread spectrum signal. The transmitted data is reproduced after correlation with the matching pn sequence. When the spreading codes are orthogonal to one another, the received signal can be correlated with a particular user signal related to the particular spreading code such that only the desired user signal related to the particular spreading code is enhanced while the other signals for all other users are not enhanced.
Each value of the spreading code is known as a chip and has a chip rate that is the same or faster than the data rate. The ratio between the chip rate and the subchannel data rate is the spreading factor.
To extend the possible range of values of the data signal, a symbol is used to represent more than two binary values. Ternary and quaternary symbols take on three and four values respectively. The concept of a symbol allows for a greater degree of information since the bit content of each symbol dictates a unique pulse shape. Depending upon the number of symbols used, an equal number of unique pulse or wave shapes exist. The information at the source is converted into symbols which are modulated and transmitted through the subchannel for demodulation at the destination.
The spreading codes in a CDMA system are chosen to minimize interference between a desired subchannel and all other subchannels. Therefore, the standard approach to demodulating the desired subchannel has been to treat all other subchannels as interference, similar to interference that manifests itself in the communication medium. Receivers designed for this process are single-user, matched filter and RAKE receivers.
Since different subchannels do interfere with each other somewhat, another approach is to demodulate all subchannels at a receiver. The receiver can listen to all of the users transmitting at once by running a decoding algorithm for each of them in parallel. This ideology is known as multiuser detection. Multiuser detection can provide a significant performance improvement over single-user receivers.
Referring to FIG. 3, a system block diagram of a prior art CDMA receiver using a multiuser detector is shown. As one skilled in this art realizes, the receiver may include such functions as radio frequency or rf down conversion and associated filtering for radio frequency channels, analog-to-digital conversion or optical signal demodulation for a specific communication media. The output of the receiver is a processed signal, either analog or digital, containing the combined spread signals of all active subchannels. The multiuser detector performs multiuser detection and outputs a plurality of signals corresponding to each active subchannel. All or a smaller number of the total number of subchannels may be processed.
Optimal multiuser detectors are computationally intensive devices performing numerous complex mathematic operations and are therefore difficult to implement economically. To minimize expense, suboptimal multiuser detectors such as linear detectors have been developed requiring less computational complexity as a compromise approximating the performance of optimal detectors. Linear detectors include decorrelators, minimum mean square error or MMSE detectors, and zero-forcing block linear equalizers or ZF-BLEs.
A system block diagram of a prior art linear multiuser detector for synchronous or asynchronous CDMA communication is shown in FIG. 4. Data output from the communication media specific receiver (as in FIG. 3) is coupled to a subchannel estimator which estimates the impulse response of each symbol transmitted in a respective subchannel. The linear detector uses the impulse response estimates along with a subchannel's spreading code to demodulate each subchannel's data. The data is output to subchannel data processing blocks for respective users.
To effect parallel detection of K subchannel users in a physical system, linear multiuser detector methods are executed as fixed gate arrays, microprocessors, digital signal processors or DSPs and the like. Fixed logic systems allow for greater system speed while microprocessor driven systems offer programming flexibility. Either implementation that is responsible for the multiuser detection performs a sequence of mathematic operations. To describe the functions, the following variables typically define the structure and operation of a linear multiuser detector:                K=the total number of users/transmitters that are active in the system.        NCC=the number of chips in a data block. The number of chips is required since with varying spreading factors this number is a measure common to all users. The number of chips is divisible by the largest spreading factor allowed. For the case of synchronous CDMA, a symbol from the user with the largest spreading factor may constitute a block of data. Therefore, NC can be reduced to be equal to the largest spreading factor.        W=the communication channel impulse response length in chips. This is generally a predefined parameter of the system.        Q(k)=the spreading factor of user k. The spreading factor is equal to the number of chips that are used to spread a symbol of user's data. A system knows the spreading factors in advance and does not need to estimate them from the received data.        NS(k)=the number of symbols sent by user k. NS(k)=NC|Q(k).        
      N    s    T    =                    ∑                  k          =          1                K            ⁢                          ⁢              N        s                  (          k          )                      =          the      ⁢                          ⁢      total      ⁢                          ⁢      number      ⁢                          ⁢      of      ⁢                          ⁢      symbols      ⁢                          ⁢              sent        .                            d(k)=the data (information) sent by user k. The data is presented in the form of a vector, where a vector is an array of data indexed by a single index variable. For the purposes of vector and matrix operations which follow, all vectors are defined as column vectors. The nth element of d(k) is the nth symbol transmitted by the kth user.        h(k)=the impulse response of the subchannel experienced by user k presented as a vector. This quantity needs to be estimated at the receiver. The receiver's estimates of the subchannel impulse responses are referred to as h(k). The elements of the vector h(k) are typically complex numbers, which model both amplitude and phase variations that can be introduced by the subchannel.        v(k)=the spreading code of user k, presented as a vector. For the purposes of linear multiuser detection, it is useful to think of vectors containing the section of the spreading code which spreads a particular symbol. Therefore, the vector v(k,n) is defined as the spreading code which is used to spread the nth symbol sent by the kth user. Mathematically, it is defined as: vi(k,n)=vi(k) for (n−1)Q(k)+1≦I≦nQ(k) and 0 for all other I, where I is the index of vector elements.        r(k)=a vector which represents user k's data, spread by the spreading sequence v(k) and transmitted through that user's subchannel h(k). The vector r(k) represents channel observations performed during the period of time when a block of data arrives. The ith element of the vector r(k) can be defined as:        
                              r          i                      (            k            )                          =                              ∑                          n              =              1                                      N              s                              (                k                )                                              ⁢                                          ⁢                                    d              n                              (                k                )                                      ⁢                                          ∑                                  j                  =                  1                                W                            ⁢                                                          ⁢                                                h                  j                                      (                    k                    )                                                  ⁢                                                      v                                          i                      -                      j                      +                      1                                                              (                                              k                        ,                        n                                            )                                                        .                                                                                        Equation        ⁢                                  ⁢        1            The signal received at the receiver includes all user signals r(k) plus noise. Therefore, we can define the received data vector r as follows:
                    r        =                                            ∑                              k                =                1                            K                        ⁢                                                  ⁢                          r                              (                k                )                                              +                      n            .                                              Equation        ⁢                                  ⁢        2            The vector n in Equation 2 represents noise introduced by the communication channel.
FIG. 5 shows a system and method of a prior art linear multiuser detector. The estimated subchannel impulse response vectors h(k) and the spreading codes v(k) are used to create a system transmission response matrix for each user k. A matrix is a block of numbers indexed by two indexing variables and is arranged as a rectangular grid, with the first indexing variable being a row index and the second indexing variable being a column index.
A system transmission response matrix for user k is typically denoted as A(k). The ith-row, nth-column element is denoted as Ai,n(k) and is defined as:
                              A                      i            ,            n                                (            k            )                          =                              ∑                          j              =              1                        W                    ⁢                                          ⁢                                    h              j                              (                k                )                                      ⁢                          v                              i                -                j                +                1                                            (                                  k                  ,                  n                                )                                                                        Equation        ⁢                                  ⁢        3            
Each column of the matrix A(k) corresponds to a matched filter response for a particular symbol sent by user k during the period of interest. Referring back to FIG. 5, the received data r is matched to a combination of all user's spreading codes and subchannel impulse responses. Therefore, A(k) contains Ns(k) matched filter responses. The columns of A(k) are of the form
                              A          n                      (            k            )                          =                  [                                          ⁢                                                    0                                                                    ⋮                                                                    0                                                                                      b                  n                                      (                    k                    )                                                                                                      0                                                                    ⋮                                                                    0                                              ⁢                                          ]                                    Equation        ⁢                                  ⁢        4            where each vector bn(k) has a dimension ofQ(k)+W−1,  Equation 5and is offset from the top of the matrix An(k) byQ(k)(n−1).  Equation 6Since the spreading codes are not periodic over symbol times; bi(k)≠bj(k) for I≠j. The elements of a vector which may be non-zero values are referred to as the support of the vector. Therefore, bn(k) is the support of An(k).
Once a system transmission matrix for each user is created, a total system transmission response matrix, denoted as A is created by concatenating the system transmission matrices for all the users as shown below:A=[A(1), . . . , A(k), . . . , A(K)].  Equation 7
In accordance with prior art modulation techniques, the elements of h(k) can be complex numbers. It then follows that the non-zero elements of A can be complex numbers.
An example total system transmission response matrix A for a hypothetical prior art multiuser detector assembled in accordance with Equations 4, 5, 6 and 7 is
                    A        =                  [                                          ⁢                                                                                                                                        b                                                  1                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                                                          b                                                  1                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                                                          b                                                  1                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  2                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                                                          b                                                  1                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  2                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                                                          b                                                  1                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  2                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  3                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                                                                  0                                                                                      b                                                  2                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  3                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                              0                                                                                                  0                                                                                      b                                                  2                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  3                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  4                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                                                                  0                                                              0                                                                                      b                                                  3                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  4                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                              0                                                                                                  0                                                              0                                                                                      b                                                  3                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  4                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  5                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                                                                  0                                                              0                                                              0                                                                                      b                                                  4                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  5                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                              0                                                                                                  0                                                              0                                                              0                                                                                      b                                                  4                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  5                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  6                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                              0                                                                                                  0                                                              0                                                              0                                                              0                                                                                      b                                                  5                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  6                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                              0                                                                                                  0                                                              0                                                              0                                                              0                                                                                      b                                                  5                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  6                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  7                          ,                          1                                                                          (                          1                          )                                                                                                            0                                                                                                  0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  6                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  7                          ,                          2                                                                          (                          1                          )                                                                                                            0                                                                                                  0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  6                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  7                          ,                          3                                                                          (                          1                          )                                                                                                                                    b                                                  8                          ,                          1                                                                          (                          1                          )                                                                                                                                                0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  7                          ,                          4                                                                          (                          1                          )                                                                                                                                    b                                                  8                          ,                          2                                                                          (                          1                          )                                                                                                                                                0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  7                          ,                          5                                                                          (                          1                          )                                                                                                                                    b                                                  8                          ,                          3                                                                          (                          1                          )                                                                                                                                                0                                                              0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  8                          ,                          4                                                                          (                          1                          )                                                                                                                                                0                                                              0                                                              0                                                              0                                                              0                                                              0                                                              0                                                                                      b                                                  8                          ,                          5                                                                          (                          1                          )                                                                                                                    ︸                                            A                                  (                  1                  )                                                      ⁢                                                  ⁢                                                                                                                                                        b                                                      1                            ,                            1                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                    0                                                                                                                                      b                                                      1                            ,                            2                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                    0                                                                                                                                      b                                                      1                            ,                            3                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                    0                                                                                                                                      b                                                      1                            ,                            4                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                    0                                                                                                                                      b                                                      1                            ,                            5                                                                                (                            2                            )                                                                                                                                                b                                                      2                            ,                            1                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                                                                                      b                                                      1                            ,                            6                                                                                (                            2                            )                                                                                                                                                b                                                      2                            ,                            2                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                                                                                      b                                                      1                            ,                            7                                                                                (                            2                            )                                                                                                                                                b                                                      2                            ,                            3                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                                                            0                                                                                              b                                                      2                            ,                            4                                                                                (                            2                            )                                                                                                                      0                                                                    0                                                                                                            0                                                                                              b                                                      2                            ,                            5                                                                                (                            2                            )                                                                                                                                                b                                                      3                            ,                            1                                                                                (                            2                            )                                                                                                                      0                                                                                                            0                                                                                              b                                                      2                            ,                            6                                                                                (                            2                            )                                                                                                                                                b                                                      3                            ,                            2                                                                                (                            2                            )                                                                                                                      0                                                                                                            0                                                                                              b                                                      2                            ,                            7                                                                                (                            2                            )                                                                                                                                                b                                                      3                            ,                            3                                                                                (                            2                            )                                                                                                                      0                                                                                                            0                                                                    0                                                                                              b                                                      3                            ,                            4                                                                                (                            2                            )                                                                                                                      0                                                                                                            0                                                                    0                                                                                              b                                                      3                            ,                            5                                                                                (                            2                            )                                                                                                                                                b                                                      4                            ,                            1                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                                              b                                                      3                            ,                            6                                                                                (                            2                            )                                                                                                                                                b                                                      4                            ,                            2                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                                              b                                                      3                            ,                            7                                                                                (                            2                            )                                                                                                                                                b                                                      4                            ,                            3                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                    0                                                                                              b                                                      4                            ,                            4                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                    0                                                                                              b                                                      4                            ,                            5                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                    0                                                                                              b                                                      4                            ,                            6                                                                                (                            2                            )                                                                                                                                                              0                                                                    0                                                                    0                                                                                              b                                                      4                            ,                            7                                                                                (                            2                            )                                                                                                                                ︸                                ⁢                                                                                              A                                  (                  2                  )                                                              ]                                    Equation        ⁢                                  ⁢        8            for two (k=2) users, A(1) and A(2) having sixteen chips in a data block (NC=16), a channel impulse response length of four (W=4) and a spreading factor for the first user of two (Q(1)=2) and a spreading factor for the second user of four (Q(2)=4). In the resultant total system transmission response matrix A, bn,i(k) denotes the ith element of the combined system and channel response for the nth symbol of the kth user.
The received data r is processed using the total system transmission response matrix A which represents a bank of matched filter responses to create a vector of matched-filter outputs which is denoted as y. The matched filtering operation is defined asy=AHr.  Equation 9
The matrix AH represents the Hermitian (or complex) transpose of the matrix A. The Hermitian transpose is defined as AijH=Āji where the over-bar denotes the operation of taking a conjugate of a complex number. The matched filter outputs are then multiplied by the inverse of an objective matrix O. The objective matrix O represents the processing which differentiates each type of linear receiver model. It is derived from the system transmission matrix A.
The zero-forcing block linear equalizer (ZF-BLE) receiver is a linear receiver with an objective matrix specified as O=AHA. The minimum mean square error block linear equalizer (MMSE-BLE) receiver is a linear receiver with an objective matrix specified as O=AHA+σ2I where σ2 is the variance of the noise present on each of the symbols of the received data vector r and the matrix I is known as an identity matrix. An identity matrix is square and symmetric with 1s on its main diagonal and zeros everywhere else. The size of the identity matrix is chosen so as to make the addition operation valid according to the rules of linear algebra.
For a decorrelator (decorrelating receiver), matrix A is simplified by ignoring the channel responses h(k), considering only the spreading codes and their cross-correlation (interference) properties. A cross-correlation matrix, commonly referred to as R, is generally constructed for decorrelator type receivers. This matrix can be constructed by assuming that W=1 and hi(k)=1 in the definition of A above (i.e. the channel response of every subchannel is an impulse). Then the cross correlation matrix R is the objective matrix O as defined for the ZF-BLE receiver. A decorrelator often serves as a sub-process of a more complex multiuser detection receiver. Once the objective matrix is created, the multiuser detector will invert the matrix, denoted as O−1.
The inverse of the objective matrix is then multiplied by the matched filter output vector y to produce estimates of the data vector d where d(estimate)=O−1y. The inversion of the objective matrix O is a complex, computationally intensive process. The number of operations required to perform this process increase as the cube of the size of the matrix O. For most asynchronous CDMA receivers, the size of O is very large which makes the process of inversion impracticable.
To overcome this limitation, and to make the system physically realizable, a numerical method due to Cholesky is used. Cholesky decomposition can significantly reduce the computational complexity of inverting the matrix O if the matrix is banded.
A banded matrix is a square matrix that contains non-zero values only on several diagonals away from the main diagonal. The number of non-zero diagonals adjacent to the main diagonal that have at least one non-zero element is referred to as bandwidth. Thus, a symmetric matrix M is said to be banded with bandwidth p ifmij=0 for all j>I+p,  Equation 10where mij is an element of M, with I being the row index and j the column index. For a banded matrix with size denoted as n and bandwidth denoted as p, Cholesky decomposition can reduce the required numeric operations of inverting the objective matrix O from varying as the cube of the size of the matrix, n3, to varying as the size of the matrix times the square of the bandwidth, np2.
As discussed above, the objective matrix for a ZF-BLE receiver is O=AHA. To illustrate ate the numeric complexity, the objective matrix for the total system response shown in Equation 6 is
                    O        =                  [                                          ⁢                                                    x                                            x                                            x                                            0                                            0                                            0                                            0                                            0                                            x                                            x                                            0                                            0                                                                    x                                            x                                            x                                            x                                            0                                            0                                            0                                            0                                            x                                            x                                            0                                            0                                                                    x                                            x                                            x                                            x                                            x                                            0                                            0                                            0                                            x                                            x                                            x                                            0                                                                    0                                            x                                            x                                            x                                            x                                            x                                            0                                            0                                            x                                            x                                            x                                            0                                                                    0                                            0                                            x                                            x                                            x                                            x                                            x                                            0                                            0                                            x                                            x                                            x                                                                    0                                            0                                            0                                            x                                            x                                            x                                            x                                            x                                            0                                            x                                            x                                            x                                                                    0                                            0                                            0                                            0                                            x                                            x                                            x                                            x                                            0                                            0                                            x                                            x                                                                    0                                            0                                            0                                            0                                            0                                            x                                            x                                            x                                            0                                            0                                            x                                            x                                                                    x                                            x                                            x                                            x                                            0                                            0                                            0                                            0                                            x                                            x                                            0                                            0                                                                    x                                            x                                            x                                            x                                            x                                            x                                            0                                            x                                            x                                            x                                            x                                            0                                                                    0                                            0                                            x                                            x                                            x                                            x                                            x                                            x                                            0                                            x                                            x                                            x                                                                    0                                            0                                            0                                            0                                            x                                            x                                            x                                            x                                            0                                            0                                            x                                            x                                              ⁢                                          ]                                    Equation        ⁢                                  ⁢        11            where zeros denote all elements that by mathematical operation yield zero and with x's representing non-zero values. If the non-zero elements of the ith row and jth column of the total system response matrix A do not have the same vector index, then the corresponding element of objective matrix O with row index I and column index j will be 0. The bandwidth of O (Equation 11) is equal to 9 since there are non-zero elements as far as nine columns away from the main diagonal.
The objective matrix O as it is constructed in the prior art receiver shown in FIG. 5 is not well banded. Therefore, Cholesky decomposition cannot be used effectively to reduce the operational complexity when inverting matrix O. However, the prior art discloses that when all users transmit with equal spreading factors, a re-arrangement of the total system transmission response matrix A can be performed prior to calculating an objective matrix O, turning matrix O into a banded matrix. A system block diagram for this process is shown in FIG. 6.
The process which computes the column re-arrangement of matrix A performs the re-arrangement without any additional information. The re-arrangement reduces the operational complexity when inverting the matrix. Once the detection procedure is complete, a user data vector d is computed, a reversed re-arrangement process is performed descrambling vector d back to its original form for further processing.
In a typical asynchronous CDMA system, the bandwidth of a re-arranged objective matrix is at least ten times less than its original size. Therefore, a savings of at least a factor of 100 in processing time is achieved when Cholesky decomposition is performed on an objective matrix based upon are-arranged total system response matrix. However, the prior art has not addressed a re-arrangement method for when different spreading factors are in use between active users.
Accordingly, there exists a need to determine a method to reduce the number of inversion steps when different spreading factors are in use.